package Greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

public class GreedyAlgorithm {
    public static void main(String[] args) {
        //定义一个保存有需要覆盖的地区的集合
        HashSet<String> allAreas = new HashSet<String>();

        //定义一个广播站Map
        HashMap<String, HashSet<String>> broadcasts = new HashMap<>();
        allAreas.add("北京");
        allAreas.add("上海");
        allAreas.add("天津");
        allAreas.add("广州");
        allAreas.add("深圳");
        allAreas.add("成都");
        allAreas.add("杭州");
        allAreas.add("大连");
        //将各个电台放入到broadcasts
        HashSet<String> hashSet1 = new HashSet<String>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");

        HashSet<String> hashSet2 = new HashSet<String>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");

        HashSet<String> hashSet3 = new HashSet<String>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");


        HashSet<String> hashSet4 = new HashSet<String>();
        hashSet4.add("上海");
        hashSet4.add("天津");

        HashSet<String> hashSet5 = new HashSet<String>();
        hashSet5.add("杭州");
        hashSet5.add("大连");

        //加入到map
        broadcasts.put("K1", hashSet1);
        broadcasts.put("K2", hashSet2);
        broadcasts.put("K3", hashSet3);
        broadcasts.put("K4", hashSet4);
        broadcasts.put("K5", hashSet5);

        //定义一个ArrayList存放最终选择的广播台
        ArrayList<String> selects = new ArrayList<>();
        //定义一个临时集合用于存放广播站的覆盖地区
        HashSet<String> tempSet = new HashSet<>();
        //定义一个maxKey 指向每一次选择的覆盖地区最广的广播站
        String maxKey = null;
        //循环所有地区的Set 循环结束条件的为allareas的size为0
        while (allAreas.size() != 0) {
            //每次开始找覆盖最大范围的广播站时应该将maxkey置空
            maxKey=null;
            //遍历 broadcasts, 找到此时覆盖范围最大的广播站的key赋给maxKey
            for (String key :
                    broadcasts.keySet()) {
                //每次循环开始需要清空tempSet
                tempSet.clear();
                //获取到该广播站的覆盖读取
                HashSet<String> areas = broadcasts.get(key);
                //加入到tempset 待会用于和allareas求交集
                tempSet.addAll(areas);
                //和allAreas取交集并将结果放入tempSet中
                tempSet.retainAll(allAreas);
                //该操作主要是为了找到本次for循环的覆盖范围最大的广播站
                if (tempSet.size() > 0 && (maxKey == null || tempSet.size() > broadcasts.get(maxKey).size())) {
                    //tempSet.size() > 0 说明有交集
                    //且当前的key所指向的广播站的覆盖的范围比之前的maxKey所指向的广播站的覆盖的范围大
                    //那么说明此时的ey所指向的广播站因被maxkey记录。
                    maxKey = key;
                }
            }
            //找到了此次循环最大的广播站的key，即maxKey != null
            if (maxKey != null) {
                //放入选择的集合中
                selects.add(maxKey);
                //放完以后，需要其所指向的广播站覆盖的范围进行remove
                allAreas.removeAll(broadcasts.get(maxKey));
            }

        }

        System.out.println("得到的选择结果是" + selects);//[K1,K2,K3,K5]
    }

}
